package com.yao.code;

/**
 * @author yaoquanwei
 * @date 2021/8/15 9:51
 */
public class Code210815 {
    /**
     * 剑指offer 10.斐波那契额数列
     *
     * @param n
     * @return
     */
    public static int fib(int n) {
        if (n == 0 || n == 1) {
            return n;
        }
        int a = 1, b = 0;
        for (int i = 1; i < n; i++) {
            a = a + b;
            b = a - b;
            a %= 1000000007;
        }
        return a;
    }

    /**
     * 剑指offer 10.青蛙跳台阶问题
     * 事实上也是斐波那契额数列的变形
     *
     * @param n
     * @return
     */
    public int numWays(int n) {
        if (n <= 1) {
            return 1;
        }
        int[] res = new int[n + 1];
        res[0] = 1;
        res[1] = 1;
        for (int i = 2; i < n + 1; i++) {
            res[i] = (res[i - 1] + res[i - 2]) % 1000000007;
        }
        return res[n];
    }

    /**
     * 剑指offer 63.股票的最大利润
     *
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        if (prices.length < 2) {
            return 0;
        }
        // 利润
        int profit = 0;
        // 临时利润
        int max = 0;
        // 买入价格
        int min = prices[0];
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] < min) {
                min = prices[i];
            } else {
                int tem = prices[i] - min;
                max = max > tem ? max : tem;
            }
            profit = max > profit ? max : profit;
        }
        return profit;
    }
}
